1. Field of the Invention
The present invention relates to the field of error correction codes such as the ones employed for wireline and wireless digital communication systems and in data storage systems. As an example, the present invention relates to iterative decoding methods that implement the Maximum A Posteriori (MAP) Algorithm.
2. Description of the Related Art
A digital communication system of both wireless and wireline type usually comprises a transmitter, a communication channel and a receiver as known by those skilled in the art.
The communication channel of such system is often noisy and introduces errors in the information being transmitted such that the information received at the receiver is different from the information transmitted.
In general, in order to correct an error of the channel transmitted through wireline and wireless environments, the digital communication system uses a protection method by which the transmitter performs a coding operation using an error correction code and the receiver corrects the error produced by the noisy channel.
Various coding schemes have been proposed and developed for performing correction of errors introduced by the channel. In particular, turbo codes (which are Forward Error Correction codes, FEC) are capable of achieving better error performance than conventional codes. Furthermore, turbo codes can achieve exceptionally low error rates in a low signal-to-noise ratio environment.
For this reason, such turbo codes can usefully be employed in wireless communications, for example in the more recent CDMA wireless communication standard.
A detailed description of turbo coding and decoding schemes can be found in “Near Shannon Limit Error-Correcting Coding and Decoding: Turbo-codes”, Berrou et al., Proc., IEEE Int'l Conf. On communications, Geneva, Switzerland, 1993, pp. 1064-1070. Particularly, turbo codes are the parallel concatenation of two or more recursive systematic convolutional codes separated by interleavers.
As known by those skilled in the art, decoding of turbo codes is often complex and involves a large amount of complex computations. Turbo decoding is typically based on a Maximum A Posteriori (MAP) algorithm which operates by calculating the maximum a posteriori probabilities for the data encoded by each constituent code.
While it has been recognized that the MAP algorithm is the optimal decoding algorithm for turbo codes, it is also recognized that implementation of the MAP decoding algorithm is very difficult in practice because of its computational complexities.
To reduce such complexities, approximations and modifications to the MAP algorithm have been developed. These include a Max-Log-MAP algorithm and a Log-MAP algorithm. The Max-Log-MAP and Log-MAP algorithms are described in detail in “A Comparison of Optimal and Sub-Optimal MAP Decoding Algorithms Operating in the Log Domain”, Robertson et al., IEEE Int'l Conf. on Communications (Seattle, Wash.), June, 1995.
To reduce the computational complexity of the MAP algorithm, the Max-Log-MAP and Log-MAP algorithms perform the entire decoding operation in the logarithmic domain. In fact, in the log domain, multiplication operations become addition operations, thus simplifying numeric computations involving multiplication.